void init()
{
    for (int i = 1; i <= n; i++)
        lg[i] = lg[i - 1] + (1 << lg[i - 1] == i);
    for (int i = 1; i <= n; i++)
        lg[i]--;
    for(int j = 0;j<M;++ j)
    {
        for(int i = 1;i+(1<<j)-1<=n;++ i)
        {
            if(!j) f[i][j] = arr[i];
            else f[i][j] = min(f[i][j-1],f[i+(1<<j-1)][j-1]);
            if(!j) f1[i][j] = arr[i];
            else f1[i][j] = max(f1[i][j-1],f1[i+(1<<j-1)][j-1]);
        }
    }
}


inline int query(int l,int r)
{
    int len  = r - l + 1;
    int k  = lg[len]/lg[2];
    return min(f[l][k],f[r-(1<<k)+1][k]);
}

inline int query1(int l,int r)
{
    int len  = r - l + 1;
    int k  = lg[len]/lg[2];
    return max(f1[l][k],f1[r-(1<<k)+1][k]);
}